package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-05-04 10:55
 */
public class BuyAndSellSocketIV {
    /**
     * leetCode 188
     * 五部曲：1.数组下标：dp[i]当前i天的最大利润 2.递推公式 :在进行k组买卖的过程中使用循环：dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i])
     * dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i])
     * @param k 最多进行k组买卖
     * @param prices 价格数组
     * @return
     */
    public int maxProfit(int k, int[] prices) {
        //创建数组
        int[][]dp=new int[prices.length][2*k+1];
        //初始化
        for(int i=0;i<2*k;i+=2){
            dp[0][i+1]=-prices[0];
        }
        //遍历
        for(int i=1;i<prices.length;++i){
            for(int j=0;j<2*k-1;j+=2){
                dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
                dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);
            }
        }
        return dp[prices.length-1][2*k];
    }
}

